package s9_树.tree4_赫夫曼树;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * <code>{@link HuffmanTree}</code>
 * <p>
 * description: Tree
 * <p>
 *
 * @author 西瓜瓜 on 2022/2/23 20:05
 *
 * 赫夫曼树
 * 1.给定n个权值作为n个叶子节点，构造一颗二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为赫夫曼树
 * 2.赫夫曼树是带权路径长度最短的树，权值较大的节点离根较近
 *
 * 路径和路径长度：
 * 1.在一棵树中，从一个节点为往下可达到的孩子或孙子节点之间的通路，称为路径
 * 2.通路中分支的数目称为路径长度
 * 3.若规定根节点的层数为1，则从根节点到第L层节点的路径长度为 L-1
 *
 * 节点的权及带权路径长度：
 * 1.若将树中节点赋给一个有某种含义的数值，则这个数值称为该节点的权
 * 2.节点的带权路径长度为：从根节点到该节点之间的路径长度与该节点的权的乘积
 * 3.树的带权路径长度为：所有叶子节点的带权路径长度之和，记为WPL，权值越大的节点离根节点越近的二叉树才是最优二叉树
 * 4.WPL最小的即为赫夫曼树
 *
 */
public class HuffmanTree {

    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node node = new HuffmanTree().huffmanTree(arr);
        node.preOrder(node);

    }

    /**
     * 创建赫夫曼树
     * @param arr
     */
    private Node huffmanTree(int[] arr) {
        List<Node> nodes = new ArrayList<>();
        // 1.遍历arr数组
        for (int value : arr) {
            nodes.add(new Node(value));
        }

        while(nodes.size() > 1) {
            // 排序
            Collections.sort(nodes);
            // 2.将arr的每个元素构成一个Node
            // 取出权值最小的两颗二叉树
            // （1）取出权值最小的节点（二叉树）
            Node leftNode = nodes.get(0);
            // （2）取出权值第二小的节点（二叉树）
            Node rightNode = nodes.get(1);
            // (3)构建一颗新的二叉树
            Node parentNode = new Node(leftNode.value + rightNode.value);
            parentNode.leftNode = leftNode;
            parentNode.rightNode = rightNode;
            // (4)从nodes中删除处理过的节点
            nodes.remove(leftNode);
            nodes.remove(rightNode);

            // 3.将Node放入到ArrayList中
            nodes.add(parentNode);
        }

        // 返回赫夫曼树的root节点
        return nodes.get(0);

    }


}

class Node implements Comparable<Node>{
    /** 节点的权值 */
    int value;
    /** 左子节点 */
    Node leftNode;
    /** 右子节点 */
    Node rightNode;

    /**
     * 前序遍历
     * @param node
     */
    public void preOrder(Node node) {
        System.out.println(node.value);
        if(node.leftNode != null) {
            preOrder(node.leftNode);
        }
        if(node.rightNode != null) {
            preOrder(node.rightNode);
        }
    }

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.value - o.value;
    }
}
